package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Permutation2 {
//another solution
 public ArrayList<ArrayList<Integer>> permuteUnique1(int[] num) {
   // Start typing your Java solution below
   // DO NOT write main() function

   // assume no duplicates
   ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
   int[] perm = new int[num.length];
   boolean[] used = new boolean[num.length];
   for (int i = 0; i < used.length; i++) {
     used[i] = false;
   }
   // difference
   Arrays.sort(num);

   permute(num, 0, perm, used, result);

   return result;
 }

 public void permute(int[] num, int level, int[] perm, boolean[] used,
     ArrayList<ArrayList<Integer>> result) {
   if (num.length == level) {
     ArrayList<Integer> x = new ArrayList<Integer>();
     for (int i = 0; i < perm.length; i++) {
       x.add(perm[i]);
     }

     result.add(x);
     return;
   }

   // used[i] = true means num[i] is used
   for (int i = 0; i < num.length; i++) {
     if (!used[i]) {
       used[i] = true;
       perm[level] = num[i];
       System.out.println("the level is " + level + " and i is " + i + " and used is " + Arrays.toString(used) + " and backtrack is " + Arrays.toString(perm));
       permute(num, level + 1, perm, used, result);
       used[i] = false;
       while (i + 1 < num.length && num[i] == num[i + 1]) {
         i++;
       }
     }
   }
 }
  
  
  // working!!!
  public static void permutateHelperDuplicate(ArrayList<Integer> prefix,
      ArrayList<Integer> rest, ArrayList<ArrayList<Integer>> result) {
    int N = 0;
    if (rest != null)
      N = rest.size();
    if (N == 0) {
      result.add(prefix);
    } else {
      for (int i = 0; i < rest.size(); i++) {

        // test if rest[i] is unique.
        boolean found = false;
        for (int j = 0; j < i; j++) {
          if (rest.get(j) == rest.get(i)) // rest[j]==rest[i]
            found = true;
        }
        if (found)
          continue;
        ArrayList<Integer> newPrefix = new ArrayList<Integer>(prefix);
        newPrefix.add(rest.get(i));
        ArrayList<Integer> newRest = new ArrayList<Integer>(rest);
        newRest.remove(i);
        permutateHelperDuplicate(newPrefix, newRest, result);
      }
    }
  }

  public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> rest = new ArrayList<Integer>();
    for (int k = 0; k < num.length; k++) {
      rest.add(num[k]);
    }
    ArrayList<Integer> intList = new ArrayList<Integer>();
    permutateHelperDuplicate(intList, rest, result);
    return result;
  }

  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    // permutateHelperDuplicate("", "1233");
    Permutation2 p = new Permutation2();
    System.out.println(p.permuteUnique1(new int[] { 1, 2, 3, 3 }).toString());
  }

}
